1. Field of the Invention:
The present invention relates to an associative storage type cache memory and in particular, to a multi-way associative storage type cache memory having a data memory and a tag memory, wherein the data memory stores a part of data in a main memory accessed by a data processing unit, the tag memory stores address tags corresponding to addresses in the main memory of the data stored in the data memory. When the address designated by the data processing unit is identical with the content stored in the tag memory, the associative storage type cache memory outputs data stored in the data memory corresponding to the address tag to the data processing unit.
2. Description of the Prior Art:
In recent years, as the functions of microprocessors have improved, there has been a marked tendency that high speed associative memories such as cache memories are embedded in microprocessor chips so as to accelerate the memory access speed that critically influences the performance of the microprocessors. Thus, the storage capacitance of the associative memory increases, wherby the associative memory occupies most of the areas of the microprocessor chip. Consequently, the performance, area, and power consumption of the associative memories largely affect those of the microprocessor.
The bit width of tag memory of the cache memories used in recent microprocessors has become relatively wide as compared with the bit width of addresses of data memory. For example, there is known a cache memory having a tag memory of 20-bit width used with data memory having 32-bit address width. Thus, the ratio of tag memory cells to all memory cells of an associative memory becomes large. In addition to reading/writing data at high speed, a cache memory has to quickly determine whether or not data has been stored therein. Thus, the cache memory has to read, write, and compare all of the bits of a tag memory having a large bit width at a time. Consequently, the power consumption of the tag memory becomes large. Thus, the power consumption of the associative memory and accordingly of the microprocessor increases.
Particularly, when the associative type cache memory has n tag memories per entry and the bit width of an address tag is W bits, data consisting of (W.times.n) bits in memory cells of the tag memories are read out and the data are subjected to comparison in n pieces of comparator having W-bit width for one data access. Thus, the power for (W.times.n) bits is consumed for one data access.
FIG. 3 is a block diagram showing an example of a conventional cache memory as a first prior art. The cache memory shown in FIG. 3 is a seven-bit-address, four-entry, two-way associative type cache memory.
In FIG. 3, address 10 supplied from a data processing unit to an address bus is composed of four-bit address tag 11, two-bit entry address 14, and one-bit byte address 15.
The cache memory comprises decoder 1, tag memories 3'a and 3'b, data memories 5a and 5b, valid bits 4a and 4b, comparators 7'a and 7'b, byte selectors 8a and 8b, and way selector 9. Decoder 1 decodes entry address 14 of address 10. Data memories 5a and 5b store data of two bytes per entry address. Valid bits 4a and 4b represent whether or not the contents stored in data memories 5a and 5b are valid, respectively. Comparators 7'a and 7'b determine whether or not data stored in data memories 5a and 5b are valid based on the result of comparison between the contents of address tag 11 and the contents of tag memories 3'a and 3'b and on valid bits 4a and 4b, respectively. Byte selectors 8a and 8b select one of byte data in memories 5a and 5b corresponding to byte address 15, respectively. Way selector 9 selects one of or none of output data of byte selectors 8a and 8b corresponding to bit signals 16a and 16b that represent determined results of comparators 7'a and 7'b, respectively.
In FIG. 3, suffixes a and b of references such as 3'a and 3'b representing tag memories and 5a and 5b representing data memories represent ways a and b, respectively. The valid bits 4a and 4b represent whether or not the contents of data memories 5a and 5b are consistent with the contents of the main memory, respectively.
Next, the operation of the cache memory will be explained.
when address 10 is supplied from the data processing unit, entry address 14 is decoded by decoder 1. The contents at the selected entry address of tag memories 3'a and 3'b are supplied to comparators 7'a and 7'b, respectively. In addition, the contents at the selected entry address of data memories 5a and 5b are supplied to byte selectors 8a and 8b, respectively. The byte data selected by byte selectors 8a and 8b are supplied to way selector 9.
When comparators 7'a or 7'b determine that the contents at the selected entry address of tag memories 3'a or 3'b are identical with address tag 11 and also valid bits 4a or 4b are active, bit signal 16a or 16b becomes active.
When there is present a way in which the contents at the selected entry address of tag memory 3'a or 3'b are identical with address tag 11, data of the way are output from way selector 9. When there is present no way in which the contents at the selected entry address of the tag memory 3'a or 3'b are identical with address tag 11, relevant data in a main memory (not shown) rather than the cache memory are accessed by data processing unit. In addition, the data are stored in data memories 5a and 5b of the cache memory.
In the cache memory explained above, the number of memory cells of tag memories increases in proportion to the number of data elements stored in the data memories. As a second prior art, there is a cache memory with a reduced number of memory cells of tag memories disclosed in JPA-2-161546 in which hardware efficiency is improved.
In the cache memory of the second prior art, in order to accomplish the aforementioned object, tag memories are divided into a plurality of bit groups according to bit order. Bit group in higher bit order is unified into one common memory which corresponds to one entry. FIG. 4 shows an example of a two-way associative type, seven-bit address, four-entry cache memory according to the second prior art.
In FIG. 4, the tag memory is divided into first tag memories 33a and 33b and second tag memories 36a and 36b of which each has two-bit width. First tag memories 33a and 33b store two high-order bits out of four bits of address tag 11. Second tag memories 36a and 36b store two lower-order bits out of four bits of address tag 11 per entry. Data memories 5a and 5b store two-byte data corresponding to a four-bit address whose higher-order bits are the two bits in first tag memories 33a and 33b and whose lower-order bits are the two bits in second tag memories 36a and 36b, respectively. In other words, data memories 5a and 5b store only data at the address whose two higher-order bits are the two bits stored in first tag memories 33a and 33b, respectively.
Thus, when the data which is read from the main memory will be stored in data memory 5a or 5b in case that both of the pair of tag memories 33a and tag memories 36a and the pair of tag memory 33b and tag memory 36b are not identical with the address tag 11, the two higher-order bits of address tag 11 must be identical with the contents of first tag memory 33a or 33b.
As explained above, in the multi-way associative type cache memory of the first prior art, whenever data access operation is performed, data of all the memory cells in tag memories having W.times.n bit size are read simultaneously and subjected to comparison in n pieces of W-bit width comparator. Thus, the power for W.times.n bits is consumed.
On the other hand, in a direct map type cache memory equivalent to a one-way associative type cache memory, whenever data access operation is performed, data is read from a W-bit width tag memory and then the contents of the tag memory and the address tag are compared over W bits. Thus, the multi-way associative type cache memory consumes the power n times as large as the direct map type cache memory. However, since the direct map type cache memory has a lower hit rate than the multi-way associative type cache memory, the performance of the microprocessor of the former type becomes poor.
In the cache memory of the second prior art having the decreased number of tag memory cells, although the power required for reading data from the tag memory cells is decreased by the amount corresponding to the decreased number of tag memory cells and the decreased load capacitance of word lines of the tag memories, whenever data access operation is performed, data must be read from (W.times.n) tag memory cells and then the address tag and the contents of the tag memories must be compared over W.times.n bits. Thus, the cache memory of the second prior art requires larger power consumption than the direct map type cache memory.